package org.example;

import java.util.Arrays;
import java.util.Collections;

public class Test2 {
    //leetcode 738 单调递增的数字 https://leetcode.cn/problems/monotone-increasing-digits/description/

    /**
     * 将n转换为字符数组，当ch[i]>ch[i+1]的时候，只需要将ch[i]-1，然后ch[i+1]以及之后的字符修改成'9'就可以了
     * 例如21->19，但是这样又会出现问题，就是当修改了ch[i]之后可能不满足ch[i]>=ch[i-1]了，那么这样该怎么做呢
     * 我们可以从后往前遍历，记录从哪个位置开始的值修改为'9'，当遇到ch[i]>ch[i+1]，ch[i]-=1，start=i+1
     * 遍历完成数组之后，将start以及之后的字符都修改为'9', 332->329->299
     * @param n
     * @return
     */
    public int monotoneIncreasingDigits(int n) {
        String s = String.valueOf(n);
        char[] ch = s.toCharArray();
        int len = ch.length, start = len;
        for (int i = len - 2; i >= 0; i--) {
            if (ch[i] > ch[i + 1]) {
                ch[i] -= 1;
                start = i + 1;
            }
        }
        for (int i = start; i < len; i++) ch[i] = '9';
        return Integer.parseInt(String.valueOf(ch));
    }
}
